\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{pdfpages}
\usepackage[frenchb]{babel}
\usepackage{graphicx}
\usepackage[numbers]{natbib}
\usepackage[nottoc, notlof, notlot]{tocbibind}
\usepackage{multicol,lipsum}
\usepackage{wrapfig}
\usepackage{textcomp}
\usepackage{fullpage}
\usepackage{frbib}
\usepackage[toc,page]{appendix} 


\title{\vspace{50pt}Rapport de Projet  \\ Compilateur Lea}
\author{CATHALA Audrey, MARIE Erik, PETIT Enguerrand,\\TESSIER Alexis, TESTA Mickaël}

\begin{document}

\begin{minipage}{0.5\linewidth} % permet de faire les deux colonnes pour mettre l'image à droite du texte
\begin{flushleft}
\textbf{Université Bordeaux 1 \\ Sciences et Technologies}\\ 
\end{flushleft}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\begin{flushright}
\includegraphics[scale = 0.4]{logo}
\end{flushright}
\end{minipage}
\vspace{4cm}


\begin{center}
\LARGE {Master 1 : \\Rapport de Projet Compilation: }
\huge \\ \textbf{\\ Compilateur LEA}
\end{center}


\vspace{4cm}


\noindent
\begin{center}
\textbf{Auteurs :} CATHALA Audrey, MARIE Erik, PETIT Enguerrand,\\TESSIER Alexis, TESTA Mickaël
\end{center}

\newpage

\tableofcontents

\newpage

\section{Cahier des charges}

\subsection{Introduction}

L'objectif du projet est de réaliser un compilateur de langage Léa ( langage élémentaire algorithmique ). Le but de ce compilateur est de prendre en entrée un programme écrit en Léa autrement dit un fichier "test.lea" et de le transformer en un programme Java, de préférence exécutable. Afin que le compilateur accepte une certaine sémantique, une liste de types et de formes nous a été fournie.  Ce projet consiste donc a établir un cahier des charges cohérents face au problème proposé.  Afin de pouvoir mettre en place le langage "Léa", il nous faut une grammaire qui correspond aux attentes du sujet. C'est à dire qu'il faut respecter les différentes formes fournies, ou, au moins,  s'appuyer un maximum dessus afin de vérifier la sémantique fournie. Et pour finir, il faut appliquer un traitement afin de transformer cette entrée en un fichier "$.java$", qui de préférence compile. Nous allons donc exposer ici les différentes phases du projet, les problèmes envisagés %?
et, pour finir, les différents choix que nous avons effectué. Vous pouvez voir en Annexe \ref{test} \& \ref{point}, un exemple de fichier lea avec le résultat en java. Nous fournissons aussi un jeu de 7 tests dans le dossier $test$, qui utilisent les classes, les structures, les appels de fonctions, les entrées / sorties ...  Nous fournissons une javadoc (simple) avec nos fonctions,  le build permet aussi de générer l'archive de notre projet.

\subsection{Phases du projet}
Ce projet s'est construit en plusieurs phases. Tout d'abord il nous fallait une grammaire correcte reconnaissant le langage "léa", c'est la partie analyseur lexical. Puis il y a la vérification des types et enfin l'écriture dans un fichier. 

\subsubsection{\indent Création d'un analyseur lexical et d'un analyseur syntaxique}
La première étape est de créer l'analyseur lexical, celui-ci nous permet de parser le fichier source en Léa. Suite à cela nous avons écris l'analyseur syntaxique, sa fonction est de nous permettre de vérifier la syntaxe du fichier source et ainsi de savoir s'il est bien écrit. Attention, dans celui que nous fournissons certaines des règles sont écrites tel que $prototype$, mais ne sont pas transformés en écriture "java" par manque de temps. La syntaxe général de notre langage "lea" est disponible en Annexe \ref{syntaxe}. 
\\
Afin de respecter la sémantique demandé, cette grammaire permet la définition des variables de manière globale, ainsi qu'au début d'un bloc. Aucune déclaration ne sera acceptée après la première instruction.\\
 Les différents types reconnues sont les types de bases($int, char, string,double,boolean $), les $maps$, les $list$ et les $set$. Nous pouvons aussi créer nos propres types, c'est à dire de définir des types grâce aux Structures et aux Classes ($struct$, $class$). Le type $Enum$ est reconnue mais n'est pas implémenté. Les $Tuples$ ne sont pas implémenté, par manque de temps.\\
Les instructions $for$,  $while$, $repeat\ while$, les affectations, $print$,$read$, les appels de fonctions, les instructions conditionnelles tel que $if$, $if\ else$, $case of$ sont reconnues et transformées en java. 

\subsubsection{\indent Création de l'arbre syntaxique}

A l'aide de l'analyseur syntaxique nous créons l'arbre syntaxique correspondant au fichier d'entrée grâce aux différentes règles créé a partir des demandes formulées. Cette structure de donnée nous permet ensuite d'effectuer la vérification des types des fonctions et des expressions, mais aussi et surtout, l'arbre nous permet d'écrire les fichiers de sortie qui constitueront le programme Java attendu.

\subsubsection{\indent Vérifications de type}
La vérification de type permet de vérifier le type des opérandes selon l'opérateur et le type de la variable qui stocke le résultat. Ici nous nous en servons pour les opérations que nous appellerons arithmétique ($+,-,/,*,\% $), mais aussi pour les formules booléennes, dans les boucles $ while$. Nous ne pouvions pas réaliser la totalité des vérifications par manque de temps, mais nous invitons par des warning l'utilisateur a vérifier lorsque cela n'est pas fait.\\
Afin d'effectuer cette vérification, nous avons donc mis en place des règles afin de vérifier les types par rapport aux types des opérandes et à l'opération.
Par exemple, le type de retour entre un $int$ et un $double$ sera un double, idem lors d'une opération arithmétique. L'addition entre un caractère et un $int$ renverra un caractère, l'addition entre un caractère et un $String$ sera un $String$.\\
Lors d'une affectation aucune transformation ne sera acceptée, c'est à dire que le type du membre droit devra être identique a celui du membre gauche. \\ Si nous avons une variable locale, son type est vérifié si jamais elle est déclarée mais que son type ne correspond pas au type attendu, il y aura alors un Warning. En effet, si nous arrêtions l'analyse nous ne pouvions pas utiliser la variable déclarée dans la boucle for, nous nous en sommes rendu compte lors des derniers tests et nous n'avons pas eu le temps de modifier notre code pour que cela fonctionne avec le type de la variable.\\

Par manque de temps, nous n'avons pas pu vérifier la totalité des types, c'est à dire que nous ne vérifions pas pour des types complexes ($map$, $list$, $set$, appel de fonction).


\subsubsection{\indent L'écriture des fichiers Java}
L'écriture du fichier $.java$ se fait essentiellement grâce au fichier $parcours.java$ qui regroupe la totalité de nos fonctions permettant l'écriture de ce dernier. \\
Afin d'écrire ce fichier, nous parcourons l'arbre et en fonction du n\oe ud où nous sommes, nous connaissons la forme que doit prendre l'écriture, à partir de là plusieurs fonctions interviennent ou se passe la main ce qui permet une écriture rapide et propre malgré le manque d'indentation. \\
C'est ici que nous décidons aussi de l'allocation des variables. S'il s'agit d'une variable locale alors nous l'allouons directement, mais si c'est une variable globale nous devons vérifier si elle l'a déjà été ou non, pour cela un booléen associé à la variable a été mis en place, nous n'avons qu'à le consulter pour savoir s'il est donc nécessaire ou non de l'allouer.\\
Une variable Globale en $lea$ sera déclarée comme une variable $static$ de la classe $Main$ alors qu'une variable de classe ne sera pas $static$. \\
Une classe déclarée en $lea$, est définit comme une classe en $Java$ dans un fichier portant le nom de cette classe. Une Structure est déclarée en une classe $static$ interne à la classe $Main$.
Une fonction/procédure de classe sera déclarée en $public$ alors qu'une fonction/procédure définie directement dans le fichier $lea$ sera définie comme une fonction $public\ static$. 
\newpage
\section{Problèmes envisagés}
Plusieurs problèmes peuvent survenir de sources différentes. Tout d'abord nous parlerons de la grammaire, puis de la vérification des types et enfin de la transformation en java.

\subsection{Problème lié à la grammaire :}
La grammaire peut reconnaitre des formes propres au langages "lea" mais qui ne sont pas encore transformable ce qui produira un Warning, ou une erreur après le signal de fin de compilation, c'est à dire à l'écriture du fichier. Il suffit donc de vérifier la construction de ces formes et de les transformer en Java.\\
\indent La non reconnaissance du this peut-être problématique aussi, mais cela n'empêchera pas le bon fonctionnement du programme tant que certaines règles sont respectées ( noms des arguments et variables différents des variables de classes).\\ Par contre, les appels de méthodes $this.fonction(...)$ fonctionnent puisque nous ne lançons qu'un warning a ce moment là.


\subsection{Problème lié à la vérification des types :}
 Lors de la vérification, il y a de grands risques d'erreurs, puisque un certains nombres de formes ne sont pas vérifiées. Les appels de fonctions peuvent être problématique puisqu'il n'y a pas de vérifications de types. Tout ceci pouvant être mis en place sur notre compilateur en modifiant les différents cas qui ne sont pas traité, mais qui sont prévue puisque des warning sont là pour impliquer l'utilisateur à la vérification. La vérification des arguments des boucles $for$, des $maps$, des $sets$ et des $list$ n'est pas effectuée. Mais tout a été prévue pour être rajoutée. En effet, la structure des fonctions a été pensé afin de signaler les cas non traité et donc il est facilement modifiable afin de rajouter ce genre de vérification. 
 
\subsection{Problème lié à la transformation en Java :}

 Un problème qui peut intervenir est l'allocation dans un environnement local, autrement dit dans une fonction puisque la variable locale est allouée lors de sa déclaration, alors qu'une variable globale est allouée lors de sa première affectation. Un second problème intervient à l'allocation, il s'agit des structures, nous n'allouons pas les variables internes à cette dernière. Il est bien entendu facilement faisable puisque tout est prévue dans le code pour savoir si la variable a été allouée ou non.  \\
\\
Nous vérifions s'il y a une fonction ou une procédure $main$, mais nous ne vérifions pas le type de retour, ni le type des arguments. Ce qui peut poser fortement problème lors de la compilation du fichier $.java$, même si nous forçons l'argument $String[] args$.  \\
\\
Un autre problème est que nous reconnaissons les prototypes mais nous ne créons pas d'interface ce qui peut avoir des conséquences sur la réutilisation.

Mais malgré ces problèmes, notre compilateur fonctionne et surtout il produit un fichier qui est compilable et exécutable.
\newpage
\section{Choix retenus}
\subsection{Du point de vue de la grammaire}

Afin de simplifier la grammaire, nous avons décidés d'ajouter des points virgules à la fin des classes et des structures, des accolades dans le $case of$. Nous avons mis en place les listes($List$), les ensembles ($Set$), et les Tables de Hachages($HashMap$), avec eux, les appels afin d'ajouter plusieurs éléments tel qu'une affection entre une liste / un ensemble avec $\{1,2,3,4\}$ ajoute les éléments $1,2,3,4$ à une liste / un ensemble et $\{(1,2),(3,4)\}$ ajoute $(1,2) $puis$ (3,4)$ a une map avec comme premier élément la clef et comme second la valeur associé. Mais les fonctions liées aux $HashMap$, aux $Set$, et aux $List$ sont acceptées, puisque nous ne lançons que des "warning" lors de l'utilisation de fonctions. Il est bien-sûr sous entendu, que pour faire des opérations liées à ces éléments il est préférable d'utiliser les fonctions qui lui sont dédiés. \\
La grammaire limite les appels de méthodes à une seule, c'est à dire que nous ne pouvons pas faire d'appels sur un autre appel (exemple : $System.out.println(...)$ sera refuser puisque nous appelons $System.out$ puis la méthode $println()$ associée). L'idée est d'éviter les erreurs complexes qui peuvent être liées à ce genre d'appels.\\
Par contre nous avons mis en place une fonction pour afficher et récupérer du texte sur les entrées/sorties standards ($print$ et $read$). La fonction $Print$ fonctionne exactement comme le $System.out.println(...)$ de $Java$.c'est à dire que l'on peut composer notre argument avec des "+".  La fonction $read$ prend en argument un $string$ et crée un "scanner" à chaque appel. 
les appels de type $t[i]$ pour obtenir le $i$-ème éléments ne sont pas implémentés, mais cela n'a pas grande importance puisqu'en effet les différents types reconnus n'ont pas besoin de ces appels car il existe des fonctions appelées $getter$ ou $setter$ par exemple avec une liste $l$, nous pouvons faire $l.get(i)$ ce qui revient à $l[i]$.
\subsection{Les vérifications de types}

Afin d'effectuer les vérifications de types nous utilisons à la fois les environnement et les arbres syntaxiques. Cette vérification est effectuée lors de la compilation. C'est à dire que lorsque le compilateur tombe sur une forme qui demande une vérification alors elle est effectuée en direct, ce qui permet de ne pas avoir à faire toute la compilation en cas d'erreur.

Certaines vérifications n'ont pas été implémentées car nous avons manqués de temps et certaines d'entre elles étaient complexes à mettre en place dans notre code :
\begin{itemize}
\item Tout d'abord les appels de fonctions ne sont pas vérifiés dans certains cas, un warning sera alors émis dans le fichier $output.txt$ et l'utilisateur devra alors vérifier le type des arguments et le type de retour de la fonction. Les cas où l'appel est vérifié est lorsque la fonction est déclarée dans le fichier et qu'il ne s'agit pas d'une méthode de classe.

\item Nous ne faisons aucune vérification de type dans les boucles $for$. Nous pouvons passer deux formes différentes, soit nous avons $[1..MAX]$ ce qui sera traduit par de $1$ à $MAX-1$ ($for( i=1, i<MAX,i++)$ ) ou alors une variable. L'utilisateur doit s'assurer que ce qu'il passe en paramètre est énumérable.

\item Les affections avec les variables de types $map of$, $set of$ ou $list of$  ne sont pas vérifiées lors de la compilation. Ce sont des types composés et malheureusement le temps ne nous a pas permis de faire ces vérifications, des warnings et les emplacements pour faire ces vérifications sont prévus. 
\item Lors d'opérations arithmétiques, le compilateur vérifie et associe les différents types possibles.\\
\end{itemize}

L'utilisateur doit être attentif aux Warning lancés dans le fichier output.txt, puisqu'il regroupe toutes les erreurs possibles de son code. Il doit par l'absence de vérification et donc en présence de Warning, vérifier de nouveau son code.  \newpage

\begin{appendices} 
Voici quelques exemples de code lea, et en parallèle le code java produit.\\

\section{Suite de Fibonacci Récursif}
\label{test}
\begin{minipage}[t]{0.5\linewidth} 
\textbf{Code lea :}
\begin{verbatim}

function fibo(n:int):int{
   if( n=0|| n=1){
      return 1;
   }
   else{
        a:int:=fibo(n-1);
        b:int:= fibo(n-2);
        return a+b;
       }
}
procedure main(){
 	a:string;
 	n:int;
 	read(a);
 	n:=Integer.parseInt(a);	
 	n:=fibo(n);
 	print("Resultat fibo ("+a+") :"+n);
}
\end{verbatim}


\end{minipage}
\vline
\begin{minipage}[t]{0.5\linewidth}
\textbf{  Code Java :}
\begin{verbatim}

 import java.util.* ;
 public class Main {
    public static int fibo(int n) 
    {
       if( n == 0 || n == 1){
          return 1;
      }
      else{
          int a = fibo(n - 1);
          int b = fibo(n - 2);
          return a + b;
       }
    }
    public 
    static void main(String[] args)
    {
       String a;
       int n;
       Scanner sc1=
           new Scanner(System.in);
       System.out.println(
          "Veuillez saisir un mot :");
       a= sc1.nextLine();
       n = Integer.parseInt(a);
       n = fibo(n);
       System.out.println(
              "Resultat fibo ("+a+
                  ") :"+n);
	   }
 }
\end{verbatim}
\end{minipage}
\newpage
\begin{minipage}[b]{0.5\linewidth}
\section{Classe Point}
\label{point}
\begin{verbatim}
Point= class {
    x : int;
    y: int;
    
    Point(){
        x:=0;
        y:=0;
    }
    
    procedure point( x1 : int, y1 :int){
        x:=x1;
        y:=y1;
    }
    
    function add( p2 : Point):Point {
        p3 : Point;
        p3.x := x + p2.x;
        p3.y := y + p2.y;
        return p3;
    }
    
    procedure afficher(){
        print ("x :"+ x + " y :"+y);
    }	
};

procedure main()
{
    p3 :Point;
    p4 :Point;
    p5 : Point;
    p4.point(1,2);
    p5.point(1,2);
    p3:=p4.add(p5);
    p3.afficher();
}
	
\end{verbatim}
donnera en java :\\
\end{minipage}
\newpage

\begin{minipage}[t]{0.5\linewidth}
\subsection*{Point.java}
\begin{verbatim}

public class Point{
    int x;
    int y;
    public Point()
    {
        x = 0;
        y = 0;
    }
    public void point(int x1,int y1)
    {
        x = x1;
        y = y1;
    }
    public Point add(Point p2) 
    {
        Point p3 = new Point();
        p3.x = x + p2.x;
        p3.y = y + p2.y;
        return p3;
    }
    public void afficher() {
        System.out.println("x :"+
            x+" y :"+y);
    }
}



\end{verbatim}
\end{minipage}
\vline
\begin{minipage}[t]{0.5\linewidth}
\subsection*{   Main.java}
\begin{verbatim}

  import java.util.* ;
  public class Main {
    public
    static void main(String[] args)
    {
        Point p3 = new Point();
        Point p4 = new Point();
        Point p5 = new Point();
        p4.point(1,2);
        p5.point(1,2);
        p3 = p4.add(p5);
        p3.afficher();
     }
 }

\end{verbatim}
\end{minipage}

\section{Syntaxe}
\label{syntaxe}
\begin{tabular}{| p{5cm}||p{10cm} |}
\hline
type & syntaxe lea \\
\hline
\hline
declaration & id : type;\\
				&  ou id : type := expression;\\
\hline
variable & id \\
	& id . id \\
\hline
structure & id = struct \{ \\
 	& declarations\\
 	& \} ;\\
\hline
classe & id = class \{ \\
	& declarations\\
	& fonctions\\
	&\}; \\
\hline
argument & id : type\\
\hline
parametre & variable \\
\hline
arguments & arguments , argument\\
				& argument \\ 
\hline
parametres & parametres , parametre\\
		   		& parametre \\ 
\hline

fonction avec & function id (arguments): $type_{retour} $\{ \\
type de retour	& declarations\\	
	& instructions\\
	& \}\\
\hline
fonction sans & procedure id (arguments)\{ \\
type de retour	& declarations\\	
	& instructions\\
	& \}\\
\hline
 fonction  & operator id (arguments): $type_{retour} $\{ \\
operateur	& declarations\\	
	& instructions\\
	& \}\\
	\hline
fonction &  id (arguments)\{ \\
constructeur & declarations\\	
	& instructions\\
	& \}\\
\hline
\end{tabular}

\begin{tabular}{|p{5cm} ||p{10cm} |}
\hline
  \multicolumn{2}{|c|}{instructions} \\
\hline
appel de fonction & nom(parametre);\\
\hline
appel de methode & id.appel de fonction\\ 
\hline
affectation & variable := expression;\\
\hline
for & for(i in [0..1])\{declarations \\
	 & instructions\} \\
     &ou \\
     &for(i in variable)\{ declarations \\
     & instructions\} \\
\hline
 while & while( expression )\{declarations \\
 	&instructions\}\\
 		
\hline
repeat  while & repeat \{ declarations \\
		&instructions\} \\
					 & while(expression);\\
\hline
case of & case (expression) of \{\\
			&   expression1: \{ instructions\}\\
			&   expression2: \{instructions\}\\
			& 	... \\
			& \} \\

\hline
if &	if(expression)\{ declarations \\
		& instructions \} 			\\
		\hline
if else & 		if(expression)\{ declarations \\
		& 			instructions \} 	\\
		&			else \{ declarations instructions \} \\

 \hline
print & print( PrintExp ); \\
\hline
read & read(variable); \\
\hline
PrintExp &  PrintExpr + (variable ou String ou caractère);  \\
			 &  ou (variable ou String ou caracère) \\
			 \hline
\hline




\end{tabular}
\vspace{1cm}

Les expressions étant de la forme expression opérateur expression ou une variable, ou une expression parenthésée, ou un entier, un réel, une chaîne de caractères, une expression de type set/map/list... Les opérateurs reconnues sont : +, -, *, \&, $||$, \%, /, $>$, $<$, !, !=, $<=$, $>=$.  
instructions, et déclarations sont des suites sans séparateur. 

\end{appendices} 
\end{document}
